package leetcode101.binary_search;

/**
 * @author Synhard
 * @version 1.0
 * @Class Code6
 * @Description 4. Median of Two Sorted Arrays
 * Given two sorted arrays nums1 and nums2 of size m and n respectively,
 * return the median of the two sorted arrays.
 *
 * Example 1:
 *
 * Input: nums1 = [1,3], nums2 = [2]
 * Output: 2.00000
 * Explanation: merged array = [1,2,3] and median is 2.
 *
 * Example 2:
 *
 * Input: nums1 = [1,2], nums2 = [3,4]
 * Output: 2.50000
 * Explanation: merged array = [1,2,3,4] and median is (2 + 3) / 2 = 2.5.
 *
 * Example 3:
 *
 * Input: nums1 = [0,0], nums2 = [0,0]
 * Output: 0.00000
 *
 * Example 4:
 *
 * Input: nums1 = [], nums2 = [1]
 * Output: 1.00000
 * Example 5:
 *
 * Input: nums1 = [2], nums2 = []
 * Output: 2.00000
 *
 * Constraints:
 *
 * nums1.length == m
 * nums2.length == n
 * 0 <= m <= 1000
 * 0 <= n <= 1000
 * 1 <= m + n <= 2000
 * -106 <= nums1[i], nums2[i] <= 106
 *  
 *
 * Follow up: The overall run time complexity should be O(log (m+n)).
 * @tel 13001321080
 * @email 823436512@qq.com
 * @date 2021-03-29 10:44
 */
public class Code6 {
    public static void main(String[] args) {
        int[] arr1 = new int[]{1, 2};
        int[] arr2 = new int[]{3, 4};
        System.out.println(findMedianSortedArrays(arr1, arr2));
    }
    public static double findMedianSortedArrays(int[] nums1, int[] nums2) {
        int m = nums1.length;
        int n = nums2.length;
        int[] arr = new int[m + n];
        int nums1Pointer = 0, nums2Pointer = 0, arrPointer = 0;
        while (nums1Pointer < nums1.length && nums2Pointer < nums2.length) {
            if (nums1[nums1Pointer] < nums2[nums2Pointer]) {
                arr[arrPointer++] = nums1[nums1Pointer++];
            } else {
                arr[arrPointer++] = nums2[nums2Pointer++];
            }
        }
        while (nums1Pointer < nums1.length) {
            arr[arrPointer++] = nums1[nums1Pointer++];
        }while (nums2Pointer < nums2.length) {
            arr[arrPointer++] = nums2[nums2Pointer++];
        }
        if (((m + n) & 1) == 0) {
            return (arr[arr.length >> 1] + arr[(arr.length >> 1) - 1]) / 2.0;
        }
        return (double) arr[arr.length >> 1];
    }
}
